package com.justnow.offer;



import java.util.*;

/**
 * @author justnow
 * Created on 2020-10-11
 * Description
 */
public class HL01 {
    public static void main(String[] args) {
        String test = "abcdbcdcbabcdefggcwa";
        String maxSubstr = findMaxSubstr(test);
        System.out.println(maxSubstr);
    }
    public static String findMaxSubstr (String str) {
        // write code here
        LinkedList<Character> list = new LinkedList<>();
        char[] array = str.toCharArray();
        Map<Integer, String> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < array.length; i++) {
            if (list.contains(array[i])) {
                res = Math.max(res, list.size());
                if (!map.containsKey(res)) {
                    int smallsize = list.size();
                    StringBuilder stringBuilder = new StringBuilder();
                    for (int j = 0; j < smallsize; j++) {
                        stringBuilder.append(list.get(j));
                    }
                    map.put(res, stringBuilder.toString());
                }
                while (!list.isEmpty() && list.contains(array[i])) {
                    list.removeFirst();
                }
            }
            list.add(array[i]);
        }
        return map.get(res);
    }
}
